package com.leetcode;


/**
 * 1234. 替换子串得到平衡字符串 (中等)
 * <p>
 * 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
 * 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
 * <p>
 * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
 * 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
 * 请返回待替换子串的最小可能长度。
 * 如果原字符串自身就是一个平衡字符串，则返回 0。
 */
public class LeetCode1234 {

    public static void main(String[] arg0) {
        String s = "QQQQ";
        System.out.println("替换子串的最小可能长度 = " + balancedString(s));
    }

    public static int balancedString(String s) {
        char[] cs = s.toCharArray();
        int length = cs.length;

        int partial = length / 4; // 要达到QWER的数量都小于等于这个值


        int[] cnt = new int[26]; // 用来记录字母出现的次数
        for (int i = 0; i < length; i++) {
            cnt[idx(cs[i])]++;
        }

        if (check(cnt, partial)) {
            return 0;
        }
        int res = length; // 最大长度就是整个替换
        // 滑动窗口
        for (int start = 0, end = 0; start < length; start++) {
            // 循环的每次end都是变成0吗？不会，还是之前记得的end开始算起
            while (end < length && !check(cnt, partial)) {
                cnt[idx(cs[end])]--;
                end++;
            }

            if (!check(cnt, partial)) {
                break; // 这里为什么是跳出而不是continue？
                // 是因为前面的内容必须包含在子串中了，前面的子串已经存在某个字母始终超过总长度1/4
            }

            res = Math.min(res, end - start);
            cnt[idx(cs[start])]++; // 这里加是因为在上面的while循环中已经减过了
        }

        return res;
    }

    public static int idx(char c) {
        return c - 'A';
    }

    public static boolean check(int[] cnt, int partial) {
        if (cnt[idx('Q')] > partial || cnt[idx('W')] > partial || cnt[idx('E')] > partial || cnt[idx('R')] > partial) {
            return false;
        }
        return true;
    }

}
